package com.hl.algor_data_struct.dynamic;

/**
 * Created by yuanhailong on 2021/10/29.
 *
 * 0 1背包问题，即背包里面的物品不能重复
 *
 * 背包问题总结公式：
 * 1)v[i][0]=v[0][j]=0
 * 2)当w[i]>j时；v[i][j]=v[i-1][j]
 * 3)当j>=w[j]时；v[i][j]=max(v[i-1][j],v[i]+v[i-1][j-w[i]])
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w={1,4,3};//物品的重量
        int[] val={1500,3000,2000};//物品的价值
        int n=val.length;//物品的个数
        int m=4; //背包的容量

        //商品价值
        int[][] v=new int[n+1][m+1];

        //记录商品放入情况
        int[][] path=new int[n+1][m+1];

        //初始化第一行和第一列为0
        //1)v[i][0]=v[0][j]=0
        {
            for (int i = 0; i < v.length; i++) {
                v[i][0] = 0;
            }
            for (int i = 0; i < v[0].length; i++) {
                v[0][i] = 0;
            }
        }

        //根据前面的公式进行动态规划
        for(int i=1;i<v.length;i++){  //有多少行
            for(int j=1;j<v[0].length;j++){  //有多少列
                //运用上面的公式进行求解
                //2)当w[i]>时；v[i][j]=v[i-1][j]
                if(w[i-1]>j){  //因为我的程序i是从1开始的 因此w[i]需要修改为w[i-1]
                    v[i][j]=v[i-1][j];
                }else {
                    //v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
                    //为了存放商品存放到背包的情况，不能直接使用上面的工时，将其转换为if-else来做更多事情
                    if(v[i-1][j]<val[i-1]+v[i-1][j-w[i-1]]){
                        v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
                        //把当前的情况记录到path【因为这里的一定是最佳情况，而我们只需要最佳（价值最大）情况】
                        path[i][j]=1;
                    }else{
                        v[i][j]=v[i-1][j];
                    }
                }
            }
        }



        /**
         * 输出填写后表
         */
        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print(v[i][j]+" ");
            }
            System.out.println();
        }


        System.out.println("================================");
        //输出最后的价值
        int i=path.length-1;   //行的最大下标
        int j=path[0].length-1;//列的最大下标

        //从后往前找
        while (i>0  && j>0){
            if(path[i][j]==1){
                System.out.printf("第%d商品放入背包\n",i);
                j-=w[i-1];
            }
            i--;
        }

    }
}
